-- utility to raise an error 
-- on an array that is *not* properly sorted
-- between start and finish.  
-- s is a string to use to inform the user 
-- about who is to blame.  

function assert_sorted (a,start,finish,s) 
   local last = a[start] 

   for i = start+1, finish do 
      assert((last <= a[i]), 
	     string.format("%s: value %s at %d\n", s, tostring(a[i]), i)) 
      last = a[i]
   end
end 

-- seed the random number generator.  
-- Probably overkill, but we only do it once (:-) 

function set_randomseed () 
   local d = os.date() .. os.clock () 
   local t = {string.byte(d,1,string.len(d))}
   local c = 1 
   for i = 1, #t do 
      _,c = math.modf(math.exp((math.log(t[i]*c))/2))
   end 
   math.randomseed (math.modf(c*10000000000000))
end

set_randomseed ()

-- fill a table of length len
-- with integers randomly chosen  
-- between lower bound lb and upper bound ub (inclusive).  

function random_table (lb, ub, len) 
   local t = {} 
   for i = 1,len do 
      t[i] = math.random(lb,ub)
   end
   return t
end 

function insertion_sort (given)
   local flag
   local t = {} 
   t[1] = given[1] 

   -- put each remaining value in given 
   -- somewhere in t.  

   -- Note use of # to return length of a gap-free array.  
   -- table.insert inserts the value at the position j, 
   -- and shifts the rest of the array upward.  

   for i=2, #(given) do 
      for j = 1, #t do 

	 flag=false 

	 -- if it's less than this entry in t
	 -- put it here

	 if given[i]<t[j] 
	 then flag=true 
	    table.insert(t,j,given[i]) 
	    break
	 end
      end

      -- if it wasn't less than any value in t,
      -- put it at the end.  

      -- table.insert(t,v) with no index j puts v at #t+1.  

      if not(flag) then table.insert(t,given[i]) end 
   end
   return t 
end 

function sort_random (lb, ub, len)
   local o = random_table (lb, ub, len)
   local n 

   n = insertion_sort(o) 

   return n
end

--[[ 

CMerge: 

Assume that a1 is sorted, and a2 is sorted.

Return a table r containing their joint 
content, globally sorted.  

That is, make sure the entries in 
a1 are in the right spots versus the
entries in a2.  

Called CMerge because it does a lot of copying.  

--]]
function cmerge (a1,a2) 
   local r = {} 

   local a1_len = #(a1)
   local a2_len = #(a2)

   local i1 = 1 
   local i2 = 1

   -- as long as either array is not fully inserted into r ... 

   while i1 <= a1_len or i2 <= a2_len do 
      
      if i1 <= a1_len and i2 <= a2_len 
      -- if both arrays still have values remaining, 
      -- insert the lesser of the two values 
      then if a1[i1] <= a2[i2] 
	 then
	    table.insert(r, a1[i1]); 
	    i1 = i1+1
	 else 
	    table.insert(r, a2[i2]); 
	    i2 = i2+1
	 end
      else
	 -- otherwise, whichever one still has values, 
	 -- take the next value from it
	 if i1 <= a1_len 
	 then 
	    table.insert(r, a1[i1]); 
	    i1 = i1+1
	 else 
	    table.insert(r, a2[i2]); 
	    i2 = i2+1
	 end
      end
   end
   return r
end

function illustrate_cmerge (lb,ub,len)  
   local a1 = sort_random (lb, ub, len)
   local a2 = sort_random (lb, ub, len)

   print("a1:", unpack(a1))
   print("a2:", unpack(a2))

   print(unpack(cmerge(a1,a2)))
end 

function split_array (a) 
   local mid = math.floor((#a)/2)
   local t1 = {} 
   local t2 = {} 

   -- copy first half to t1 

   for i = 1, mid do 
      table.insert(t1, a[i])
   end
   
   -- copy second half to t2 

   for i = mid+1, #a do 
      table.insert(t2, a[i])
   end

   -- return em both 

   return t1,t2
end 

function cmerge_sort (a) 
   if #a <= 1 
   then
      return a 
   else
      local t1,t2 = split_array(a)

      -- solve both subproblems recursively,
      -- then cmerge the sorted results 

      return cmerge(cmerge_sort(t1),
		    cmerge_sort(t2))
   end
end 

function cmerge_sort_random (lb, ub, len)
   local o = random_table (lb, ub, len)
   local n 

   n = cmerge_sort(o) 
   assert_sorted(n,1,#n,"cmerge, unsorted result")
   return n
end

--[[

	Homework 3

	]]--
	
function merge_sort( sort )

	local temp = {}
	
	merge_sort_1( sort, temp, 1, #sort )
	
	return sort

end

function merge_sort_1( sort, temp, start, finish )

	local mid = math.floor( ( start + finish ) / 2 )
	
	if start == finish then
		return
	end

	merge_sort_1( sort, temp, start, mid )
	merge_sort_1( sort, temp, mid + 1, finish )
	
	merge( sort, temp, start, mid + 1, finish )

end

function merge( sort, temp, start, mid, finish )
	local index, i, j = 1, start, mid
	
	while i < mid and j <= finish do
	
		if sort[i] < sort[j] then
			temp[ index ] = sort[i]
			i = i + 1
		else
			temp[ index ] = sort[j]
			j = j + 1
		end
		
		index = index + 1
	end
	
	while i < mid do
		temp[ index ] = sort[i]
		index = index + 1
		i = i + 1
	end
	
	while j <= finish do
		temp[ index ] = sort[j]
		index = index + 1
		j = j + 1
	end
	
	while index > 1 do
		index = index - 1
		sort[ start + index - 1 ] = temp[ index ]
	end
end

function merge_sort_2( sort )
	local temp = {}
	
	merge_sort_1_2( sort, temp, 1, #sort, true )
	
	return temp
end

function merge_sort_1_2( sort, temp, start, finish, state )

	local mid = math.floor( ( start + finish ) / 2 )
	
	if start == finish then
		temp[start] = sort[start]
		return
	end
	
	merge_sort_1_2( sort, temp, start, mid, not state )
	merge_sort_1_2( sort, temp, mid + 1, finish, not state )
	
	merge_2( sort, temp, start, mid + 1, finish, state )

end

function merge_2( sort, temp, start, mid, finish, state )
	local index, i, j = start, start, mid
	
	if state == false then
		sort,temp=temp,sort
	end
	
	while i < mid and j <= finish do
	
		if sort[i] < sort[j] then
			temp[ index ] = sort[i]
			i = i + 1
		else
			temp[ index ] = sort[j]
			j = j + 1
		end
		
		index = index + 1
	end
	
	while i < mid do
		temp[ index ] = sort[i]
		index = index + 1
		i = i + 1
	end
	
	while j <= finish do
		temp[ index ] = sort[j]
		index = index + 1
		j = j + 1
	end
	
end

--[[
for i=1, 132 do 
	local a = merge_sort_2( random_table( 0, 10000000, i ) )
	
	assert_sorted( a, 1, #a, "Merge sort")
end
]]--
--[[
local arr = {10,9,8,55,12,7,6,63,5,42,4,3,2,1}

merge_sort( arr )

for k, v in pairs( arr ) do
	print( k, v )
end
]]

--[[
for i=1000, 101000, 5000 do

	local sortTbl = random_table( 0, 10000000, i )
	local sortTbl2 = {}
	
	for k, v in ipairs( sortTbl ) do
		sortTbl2[ k ] = v
	end
	
	local prin = tostring(i) .. "\t"
	
	local start = os.clock()
	merge_sort( sortTbl )
	prin = prin  .. tostring(os.clock() - start) .. "\t"
	assert_sorted( sortTbl, 1, #sortTbl, "Merge sort")
	
	start = os.clock()
	sortTbl2 = cmerge_sort( sortTbl2 )
	prin = prin  .. tostring(os.clock() - start)
	assert_sorted( sortTbl2, 1, #sortTbl2, "cMerge sort")
	
	print( prin )
	
end ]]--



function ApplyCount( tbl )

	local count = 0
	local newTbl = {}
	
	local CountMeta = {
		__lt = function( a, b )
			count = count + 1
			return a.Val < b.Val
		end,
		__le = function( a, b )
			count = count + 1
			return a.Val <= b.Val
		end,
		__tostring = function( a )
			return a.Val
		end
	}
	
	for k, v in ipairs( tbl ) do
		newTbl[ k ] = setmetatable( { Val = v }, CountMeta )
	end
	
	newTbl.Count = function()
		return count
	end
	
	return newTbl

end


function Benchmarch_sort( tbl, repetitions, func, name )
	
	local SumTime = 0
	local Count = 0
	
	for i=1, repetitions do
	
		local sortTbl = ApplyCount( tbl )
		
		local start = os.clock()
		local Sorted = func( sortTbl )
		SumTime = SumTime + (os.clock() - start)
		Count = Count + sortTbl.Count()
		
		assert_sorted( Sorted, 1, #Sorted, name)
		
	end
	
	SumTime = SumTime / repetitions
	Count = Count / repetitions
	
	return SumTime, Count

end

function Benchmarch( tblSize, repetitions, ... )
	
	local RandomTbl = random_table( 0, 10000000, tblSize )
	local Str = tblSize
	local Str2 = ""
	
	for k, func in ipairs( arg ) do
		local MergeTime, MergeCount = Benchmarch_sort( RandomTbl, repetitions, func, "Func " .. k )
		
		Str = Str .. "\t" .. MergeTime
		Str2 = Str2 .. "\t" .. MergeCount
	end
	
	print( Str .. Str2 )

end

function merge_couting( start, reps, step, ... )
	for i=1, reps do
		Benchmarch( start + (i-1) * step, 5, ... )
	end
end

--merge_couting( 1000, 40, 10000, merge_sort, cmerge_sort )
merge_couting( 1000, 40, 10000, cmerge_sort, merge_sort, merge_sort_2 )

